/*
 * @lc app=leetcode.cn id=399 lang=javascript
 *
 * [399] 除法求值
 */

// @lc code=start
/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
var calcEquation = function (equations, values, queries) {
  let hash = new Map();
  let res = [];

  for (let i = 0; i < equations.length; i++) {
    let item = equations[i];
    let value = values[i];
    if (!hash.has(item[0])) {
      hash.set(item[0], new Map([[item[1], value]]));
    } else {
      hash.get(item[0]).set(item[1], value);
    }
    if (!hash.has(item[1])) {
      hash.set(item[1], new Map([[item[0], 1 / value]]));
    } else {
      hash.get(item[1]).set(item[0], 1 / value);
    }
  }

  for (let item of queries) {
    let [tar, src] = item;
    if (!hash.has(tar) || !hash.has(src)) {
      res.push(`-1.0`);
      continue;
    }
    if (tar === src) {
      res.push(`1.0`);
      continue;
    }
    let set = new Set();
    function dfs(a, b, value) {
      set.add(a);
      let map = hash.get(a);
      if (set.has(b)) return `-1`;
      if (map.has(b)) {
        return value * map.get(b);
      } else {
        let temp='-1'
        for (let item of [...map]) {
          let [tar, v] = item;
          if (set.has(tar)) {
            continue;
          }
         let temp=dfs(tar, b, value * v)
         if(temp!=="-1")return temp
        }
        return temp
      }
    }
    res.push(dfs(tar, src, 1));
  }
  return res;
};
// @lc code=end
calcEquation(
  [["x1","x2"],["x2","x3"],["x3","x4"],["x4","x5"]],
  [3.0,4.0,5.0,6.0],
  [["x1","x5"],["x5","x2"],["x2","x4"],["x2","x2"],["x2","x9"],["x9","x9"]]
);
